#include <stdio.h>
#include "template.h"
void pre_decl(void) {
puts("/*");++nr;
puts("vim: syntax=c");++nr;
puts("*/");++nr;
puts("");++nr;
puts("#if PACC_ASSERT");++nr;
puts("#undef NDEBUG");++nr;
puts("#else");++nr;
puts("#define NDEBUG 1");++nr;
puts("#endif");++nr;
puts("#define PACC_XGLUE(a, b) a ## _ ## b");++nr;
puts("#define PACC_GLUE(a, b) PACC_XGLUE(a, b)");++nr;
puts("#define PACC_SYM(s) PACC_GLUE(PACC_NAME, s)");++nr;
puts("#define PACC_TRACE if (PACC_CAN_TRACE && PACC_SYM(trace))");++nr;
puts("");++nr;
puts("#include <assert.h>");++nr;
puts("#include <ctype.h>");++nr;
puts("#include <stdarg.h>");++nr;
puts("#include <stdint.h>");++nr;
puts("#include <stdio.h>");++nr;
puts("#include <stdlib.h>");++nr;
puts("#include <string.h>");++nr;
puts("");++nr;
puts("int PACC_SYM(trace) = 0;");++nr;
puts("");++nr;
puts("static void pacc_panic(const char *e) {");++nr;
puts("    fprintf(stderr, \"pacc: panic: %s\\n\", e);");++nr;
puts("    exit(1);");++nr;
puts("}");++nr;
puts("");++nr;
puts("static void pacc_nomem(void) { pacc_panic(\"out of memory\"); }");++nr;
puts("");++nr;
puts("enum pacc_status {");++nr;
puts("    no_parse, parsed, evaluated, uncomputed");++nr;
puts("};");++nr;
puts("");++nr;
puts("typedef size_t *ref_t;");++nr;
puts("");++nr;
puts("struct _pacc_coord {");++nr;
puts("    unsigned int line;");++nr;
puts("    unsigned int col;");++nr;
puts("};");++nr;
puts("");++nr;
puts("struct _pacc_coord_memo {");++nr;
puts("    size_t n;");++nr;
puts("    struct _pacc_coord c;");++nr;
puts("};");++nr;
puts("");++nr;
}
void pre_engine(void) {
puts("");++nr;
puts("/* an intermediate result, or \"mid\" */");++nr;
puts("struct pacc_mid {");++nr;
puts("    /* Where in the matrix are we? Note that the bottom two bits of rule");++nr;
puts("     * also encode a status. */");++nr;
puts("    long rule; size_t col;");++nr;
puts("    size_t remainder; /* unparsed string */");++nr;
puts("    long expr_id; /* id of the expression to evaluate, yielding... */");++nr;
puts("    union PACC_SYM(vals) value; /* ... the semantic value */");++nr;
puts("    struct {");++nr;
puts("        long call_id; /* a call */");++nr;
puts("        size_t col; /* a column */");++nr;
puts("    } *evlis;");++nr;
puts("    size_t ev_alloc;");++nr;
puts("    size_t ev_valid;");++nr;
puts("};");++nr;
puts("");++nr;
puts("#define _pacc_MIDS_PER_BLK (1024 / sizeof(struct pacc_mid) - 1)");++nr;
puts("");++nr;
puts("/* a block of mids */");++nr;
puts("struct pacc_blk {");++nr;
puts("    struct pacc_blk *next;");++nr;
puts("    struct pacc_mid mid[_pacc_MIDS_PER_BLK];");++nr;
puts("};");++nr;
puts("");++nr;
puts("/* a hash bucket */");++nr;
puts("struct pacc_bkt {");++nr;
puts("    struct pacc_blk *blk;");++nr;
puts("    unsigned int valid;");++nr;
puts("};");++nr;
puts("");++nr;
puts("static struct pacc_mid *cur;");++nr;
puts("");++nr;
puts("static void _pacc_save_core() __attribute__((unused));");++nr;
puts("static void _pacc_save_core(long c, size_t col) {");++nr;
puts("    PACC_TRACE fprintf(stderr, \"_pacc_save_core(%ld, %zu)\\n\", c, col);");++nr;
puts("    if (cur->ev_valid == cur->ev_alloc) {");++nr;
puts("        cur->ev_alloc = cur->ev_alloc * 2 + 1;");++nr;
puts("        cur->evlis = realloc(cur->evlis, cur->ev_alloc * sizeof(*cur->evlis));");++nr;
puts("        if (!cur->evlis) pacc_nomem();");++nr;
puts("    }");++nr;
puts("    cur->evlis[cur->ev_valid].call_id = c;");++nr;
puts("    cur->evlis[cur->ev_valid].col = col;");++nr;
puts("    ++cur->ev_valid;");++nr;
puts("}");++nr;
puts("");++nr;
puts("/* a pacc parser */");++nr;
puts("struct pacc_parser {");++nr;
puts("    unsigned char *string;");++nr;
puts("    size_t input_length;");++nr;
puts("    PACC_TYPE value;");++nr;
puts("    struct pacc_bkt *m_bkt;");++nr;
puts("    unsigned int m_bkt_cnt;");++nr;
puts("    //unsigned char *m_valid;");++nr;
puts("    //unsigned char m_chain_max;");++nr;
puts("");++nr;
puts("    unsigned char *stack; /* the stack */");++nr;
puts("    unsigned char *sp; /* next slot in stack */");++nr;
puts("    unsigned char *stack_alloc; /* last slot in stack */");++nr;
puts("");++nr;
puts("    /* Dynamic array of error strings */");++nr;
puts("    char **err;");++nr;
puts("    size_t err_alloc;");++nr;
puts("    size_t err_valid;");++nr;
puts("    /* The highest column to have associated error */");++nr;
puts("    size_t err_col;");++nr;
puts("");++nr;
puts("    /* Dynamic array of co-ordinates */");++nr;
puts("    struct _pacc_coord_memo *coord;");++nr;
puts("    size_t coord_alloc;");++nr;
puts("    size_t coord_valid;");++nr;
puts("};");++nr;
puts("");++nr;
puts("static void _pacc_push(void *x, size_t s, struct pacc_parser *p) {");++nr;
puts("    if (p->sp + s >= p->stack_alloc) {");++nr;
puts("        size_t l = 2 * (p->stack_alloc - p->stack) + s;");++nr;
puts("        unsigned char *n = realloc(p->stack, l);");++nr;
puts("        if (!n) pacc_nomem();");++nr;
puts("        p->sp = n + (p->sp - p->stack);");++nr;
puts("        p->stack = n;");++nr;
puts("        p->stack_alloc = n + l + 1;");++nr;
puts("    }");++nr;
puts("    assert(p->sp >= p->stack && p->sp + s < p->stack_alloc);");++nr;
puts("    memcpy(p->sp, x, s);");++nr;
puts("    p->sp += s;");++nr;
puts("}");++nr;
puts("");++nr;
puts("#define _pacc_Push(v) _pacc_push(&(v), sizeof (v), _pacc)");++nr;
puts("");++nr;
puts("static void *_pacc_pop(size_t s, struct pacc_parser *p) {");++nr;
puts("    assert(p->sp - s >= p->stack);");++nr;
puts("    p->sp -= s;");++nr;
puts("    return p->sp;");++nr;
puts("}");++nr;
puts("");++nr;
puts("#define _pacc_Pop(v) memcpy(&(v), _pacc_pop(sizeof (v), _pacc), sizeof (v))");++nr;
puts("#define _pacc_Discard(v) ((void)_pacc_pop(sizeof (v), _pacc))");++nr;
puts("");++nr;
puts("#define ref() (&cur->col)");++nr;
puts("#define ref_0(a) (_pacc->string[*a])");++nr;
puts("#define ref_dup(a) (_pacc_ref_dup((a), _pacc))");++nr;
puts("#define ref_len(a) ((a)[1] - (a)[0])");++nr;
puts("#define ref_ptr(a) (_pacc->string + *(a))");++nr;
puts("#define ref_str() (_pacc_ref_dup(ref(), _pacc))");++nr;
puts("#define ref_streq(a, b) (_pacc_ref_streq((a), (b), _pacc))");++nr;
puts("");++nr;
puts("static char *_pacc_ref_dup() __attribute__((unused));");++nr;
puts("static char *_pacc_ref_dup(ref_t a, struct pacc_parser *p) {");++nr;
puts("    char *restrict r;");++nr;
puts("    const char *restrict s;");++nr;
puts("    size_t l;");++nr;
puts("");++nr;
puts("    l = a[1] - a[0];");++nr;
puts("    r = realloc(0, l + 1); if (!r) pacc_nomem();");++nr;
puts("    s = (char *)p->string + a[0];");++nr;
puts("    strncpy(r, s, l);");++nr;
puts("    r[l] = '\\0';");++nr;
puts("    return r;");++nr;
puts("}");++nr;
puts("");++nr;
puts("");++nr;
puts("// Copyright (c) 2008-2010 Bjoern Hoehrmann <bjoern@hoehrmann.de>");++nr;
puts("// See http://bjoern.hoehrmann.de/utf-8/decoder/dfa/ for details.");++nr;
puts("");++nr;
puts("#define PACC_UTF8_ACCEPT 0");++nr;
puts("#define PACC_UTF8_REJECT 12");++nr;
puts("");++nr;
puts("static const uint8_t utf8d[] = {");++nr;
puts("  // The first part of the table maps bytes to character classes that");++nr;
puts("  // to reduce the size of the transition table and create bitmasks.");++nr;
puts("   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,");++nr;
puts("   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,");++nr;
puts("   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,");++nr;
puts("   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,");++nr;
puts("   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,  9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,");++nr;
puts("   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,");++nr;
puts("   8,8,2,2,2,2,2,2,2,2,2,2,2,2,2,2,  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,");++nr;
puts("  10,3,3,3,3,3,3,3,3,3,3,3,3,4,3,3, 11,6,6,6,5,8,8,8,8,8,8,8,8,8,8,8,");++nr;
puts("");++nr;
puts("  // The second part is a transition table that maps a combination");++nr;
puts("  // of a state of the automaton and a character class to a state.");++nr;
puts("   0,12,24,36,60,96,84,12,12,12,48,72, 12,12,12,12,12,12,12,12,12,12,12,12,");++nr;
puts("  12, 0,12,12,12,12,12, 0,12, 0,12,12, 12,24,12,12,12,12,12,24,12,24,12,12,");++nr;
puts("  12,12,12,12,12,12,12,24,12,12,12,12, 12,24,12,12,12,12,12,12,12,24,12,12,");++nr;
puts("  12,12,12,12,12,12,12,36,12,36,12,12, 12,36,12,12,12,12,12,36,12,36,12,12,");++nr;
puts("  12,36,12,12,12,12,12,12,12,12,12,12, ");++nr;
puts("};");++nr;
puts("");++nr;
puts("inline static uint32_t");++nr;
puts("pacc_decode(uint32_t* state, uint32_t* codep, uint32_t byte) {");++nr;
puts("  uint32_t type = utf8d[byte];");++nr;
puts("");++nr;
puts("  *codep = (*state != PACC_UTF8_ACCEPT) ?");++nr;
puts("    (byte & 0x3fu) | (*codep << 6) :");++nr;
puts("    (0xff >> type) & (byte);");++nr;
puts("");++nr;
puts("  *state = utf8d[256 + *state + type];");++nr;
puts("  return *state;");++nr;
puts("}");++nr;
puts("");++nr;
puts("/*");++nr;
puts("");++nr;
puts("License");++nr;
puts("");++nr;
puts("Copyright (c) 2008-2009 Bjoern Hoehrmann <bjoern@hoehrmann.de>");++nr;
puts("");++nr;
puts("Permission is hereby granted, free of charge, to any person obtaining a");++nr;
puts("copy of this software and associated documentation files (the");++nr;
puts("\"Software\"), to deal in the Software without restriction, including");++nr;
puts("without limitation the rights to use, copy, modify, merge, publish,");++nr;
puts("distribute, sublicense, and/or sell copies of the Software, and to");++nr;
puts("permit persons to whom the Software is furnished to do so, subject to");++nr;
puts("the following conditions:");++nr;
puts("");++nr;
puts("The above copyright notice and this permission notice shall be included");++nr;
puts("in all copies or substantial portions of the Software.");++nr;
puts("");++nr;
puts("THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS");++nr;
puts("OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF");++nr;
puts("MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.");++nr;
puts("IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY");++nr;
puts("CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,");++nr;
puts("TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE");++nr;
puts("SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.");++nr;
puts("");++nr;
puts("*/");++nr;
puts("");++nr;
puts("/* _pacc_utf8_char attempts to read a single UTF8 encoded character from");++nr;
puts(" * the string p with length m. Its return value is the number of bytes");++nr;
puts(" * in the character, 0 in case of error; *c holds the character read. */");++nr;
puts("static int _pacc_utf8_char(unsigned char *p, int m, uint32_t *c) {");++nr;
puts("    uint32_t state = PACC_UTF8_ACCEPT;");++nr;
puts("    int i = 0;");++nr;
puts("    do");++nr;
puts("        if (state == PACC_UTF8_REJECT || i == m) return 0;");++nr;
puts("    while (pacc_decode(&state, c, p[i++]));");++nr;
puts("    return i;");++nr;
puts("}");++nr;
puts("");++nr;
puts("static int _pacc_ref_streq() __attribute__((unused));");++nr;
puts("static int _pacc_ref_streq(ref_t a, char *b, struct pacc_parser *p) {");++nr;
puts("    /* XXX this could be made quicker */");++nr;
puts("    if (strlen(b) != (size_t)(a[1] - a[0])) return 0;");++nr;
puts("    return strncmp((const char *)p->string + a[0], b, a[1] - a[0]) == 0; ");++nr;
puts("}");++nr;
puts("");++nr;
puts("/* Find the largest available prime which is smaller than the target");++nr;
puts(" * bucket count. This exponential selection of primes was generated by");++nr;
puts(" * Dan Bernstein's primegen-0.97 package, using the following:");++nr;
puts("");++nr;
puts("perl -le '$x=1;while(($e=int(exp($x/1)))<2**32){print \"./primes \",$e,\" \",100+$e,\" | sed 1q\";++$x}' | sh");++nr;
puts("");++nr;
puts(" * except that I replaced 2 with 3.");++nr;
puts(" */");++nr;
puts("static void _pacc_set_bkt_cnt(struct pacc_parser *p) {");++nr;
puts("    static unsigned int primes[] = {");++nr;
puts("        3, 7, 23, 59, 149, 409, 1097, 2999, 8111, 22027, 59879, 162779, 442439,");++nr;
puts("        1202609, 3269029, 8886113, 24154957, 65659969, 178482319, 485165237,");++nr;
puts("        1318815761, 3584912873U");++nr;
puts("    };");++nr;
puts("    int i, p_sz = sizeof(primes) / sizeof(*primes);");++nr;
puts("    unsigned long max = n_rules * (p->input_length + 1) / 100;");++nr;
puts("    //fprintf(stderr, \"rules = %ld, length = %ld, max == %ld\\n\", n_rules, p->input_length, max);");++nr;
puts("");++nr;
puts("    for (i = 1; i < p_sz; ++i)");++nr;
puts("        if (primes[i] > max) break;");++nr;
puts("    p->m_bkt_cnt = primes[i - 1];");++nr;
puts("}");++nr;
puts("");++nr;
puts("struct pacc_parser *PACC_SYM(new)(void) {");++nr;
puts("    struct pacc_parser *p;");++nr;
puts("");++nr;
puts("    p = realloc(0, sizeof *p);");++nr;
puts("    if (!p) pacc_nomem();");++nr;
puts("    //p->m_chain_max = 0;");++nr;
puts("    p->sp = 0;");++nr;
puts("    p->stack = p->stack_alloc = 0;");++nr;
puts("    p->err = 0;");++nr;
puts("    p->err_alloc = p->err_valid = 0;");++nr;
puts("    p->err_col = 0;");++nr;
puts("    p->coord = 0;");++nr;
puts("    p->coord_alloc = p->coord_valid = 0;");++nr;
puts("    return p;");++nr;
puts("}");++nr;
puts("");++nr;
puts("void PACC_SYM(input)(struct pacc_parser *p, char *s, size_t l) {");++nr;
puts("    unsigned int i;");++nr;
puts("");++nr;
puts("    p->string = (unsigned char *)s;");++nr;
puts("    p->input_length = l;");++nr;
puts("    _pacc_set_bkt_cnt(p);");++nr;
puts("    p->m_bkt = realloc(0, sizeof(struct pacc_bkt) * p->m_bkt_cnt);");++nr;
puts("    if (!p->m_bkt) pacc_nomem();");++nr;
puts("    //p->m_valid = realloc(0, 2 * p->m_bkt_cnt);");++nr;
puts("    for (i = 0; i < p->m_bkt_cnt; ++i) {");++nr;
puts("        p->m_bkt[i].blk = 0;");++nr;
puts("        p->m_bkt[i].valid = 0;");++nr;
puts("        //p->m_valid[i * 2] = 0; /* valid */");++nr;
puts("        //p->m_valid[i * 2 + 1] = 0; /* allocated */");++nr;
puts("    }");++nr;
puts("}");++nr;
puts("");++nr;
puts("static void _pacc_destroy_blk_chain(struct pacc_blk *blk) {");++nr;
puts("    if (blk) {");++nr;
puts("        _pacc_destroy_blk_chain(blk->next);");++nr;
puts("        free(blk);");++nr;
puts("    }");++nr;
puts("}");++nr;
puts("");++nr;
puts("static void _pacc_destroy_bucket(struct pacc_bkt *bkt) {");++nr;
puts("    unsigned int i;");++nr;
puts("    struct pacc_blk *blk = bkt->blk;");++nr;
puts("");++nr;
puts("    for (i = 0; i < bkt->valid; ++i) {");++nr;
puts("        struct pacc_mid *m;");++nr;
puts("");++nr;
puts("        if (i > 0 && i % _pacc_MIDS_PER_BLK == 0)");++nr;
puts("            blk = blk->next;");++nr;
puts("        m = blk->mid + i % _pacc_MIDS_PER_BLK;");++nr;
puts("        free(m->evlis);");++nr;
puts("    }");++nr;
puts("    _pacc_destroy_blk_chain(bkt->blk);");++nr;
puts("}");++nr;
puts("");++nr;
puts("void PACC_SYM(destroy)(struct pacc_parser *p) {");++nr;
puts("    unsigned int i;");++nr;
puts("");++nr;
puts("    for (i = 0; i < p->m_bkt_cnt; ++i)");++nr;
puts("        _pacc_destroy_bucket(p->m_bkt + i);");++nr;
puts("    free(p->m_bkt);");++nr;
puts("    free(p->err);");++nr;
puts("    free(p->coord);");++nr;
puts("    free(p->stack);");++nr;
puts("    free(p);");++nr;
puts("}");++nr;
puts("");++nr;
puts("/* hash table */");++nr;
puts("static struct pacc_mid *_pacc_result(struct pacc_parser *p,");++nr;
puts("        size_t col, long rule) {");++nr;
puts("    unsigned int i;");++nr;
puts("    unsigned int h;");++nr;
puts("    struct pacc_blk *blk;");++nr;
puts("    struct pacc_bkt *bkt;");++nr;
puts("    struct pacc_mid *r;");++nr;
puts("");++nr;
puts("    assert(col < p->input_length + 1);");++nr;
puts("    PACC_TRACE fprintf(stderr, \"_pacc_result(%zu, %ld)\\n\", col, rule);");++nr;
puts("    h = (col + (rule << 6) + (rule << 16) - rule) % p->m_bkt_cnt;");++nr;
puts("    bkt = p->m_bkt + h;");++nr;
puts("    blk = bkt->blk;");++nr;
puts("    r = blk->mid;");++nr;
puts("    for (i = 0; i < bkt->valid; ++i, ++r) {");++nr;
puts("        if (i > 0 && i % _pacc_MIDS_PER_BLK == 0) {");++nr;
puts("            blk = blk->next;");++nr;
puts("            r = blk->mid;");++nr;
puts("        }");++nr;
puts("        if (r->col == col && r->rule >> 4 == rule)");++nr;
puts("            return r;");++nr;
puts("    }");++nr;
puts("    if (bkt->valid++ % _pacc_MIDS_PER_BLK == 0) {");++nr;
puts("        struct pacc_blk *b = realloc(0, sizeof *b);");++nr;
puts("        if (!b) pacc_nomem();");++nr;
puts("        if (blk) blk->next = b;");++nr;
puts("        else bkt->blk = b;");++nr;
puts("        blk = b;");++nr;
puts("        blk->next = 0;");++nr;
puts("        r = blk->mid;");++nr;
puts("    }");++nr;
puts("    /* Initialize the new element. */");++nr;
puts("    r->col = col; r->rule = rule << 4 | uncomputed;");++nr;
puts("    r->evlis = 0;");++nr;
puts("    r->ev_alloc = r->ev_valid = 0;");++nr;
puts("    /* Correct use of a side effect in an (unfailing) assert. */");++nr;
puts("    assert((r->expr_id = 0) == 0);");++nr;
puts("    return r;");++nr;
puts("}");++nr;
puts("");++nr;
puts("static int _pacc_error(struct pacc_parser *_pacc, char *what, size_t col) {");++nr;
puts("    int doit, append;");++nr;
puts("");++nr;
puts("    PACC_TRACE fprintf(stderr, \"_pacc_error(%s, %zu)\\n\", what, col);");++nr;
puts("    append = doit = 1;");++nr;
puts("    if (col > _pacc->err_col) append = 0;");++nr;
puts("    else if (col == _pacc->err_col) {");++nr;
puts("        size_t i;");++nr;
puts("        for (i = 0; i < _pacc->err_valid; ++i) {");++nr;
puts("            if (strcmp(_pacc->err[i], what) == 0) doit = 0;");++nr;
puts("        }");++nr;
puts("    } else doit = 0;");++nr;
puts("    if (doit) {");++nr;
puts("        if (append) ++_pacc->err_valid;");++nr;
puts("        else _pacc->err_valid = 1;");++nr;
puts("        if (_pacc->err_valid > _pacc->err_alloc) {");++nr;
puts("            _pacc->err_alloc = 2 * _pacc->err_alloc + 1;");++nr;
puts("            _pacc->err = realloc(_pacc->err, _pacc->err_alloc * sizeof(char *));");++nr;
puts("            if (!_pacc->err) pacc_nomem();");++nr;
puts("        }");++nr;
puts("        _pacc->err[_pacc->err_valid - 1] = what;");++nr;
puts("        _pacc->err_col = col;");++nr;
puts("    }");++nr;
puts("    return 0; /* for the fail() macro */");++nr;
puts("}");++nr;
puts("");++nr;
puts("/* Given a parser p, and a column col, return the \"coordinates\" in a");++nr;
puts(" * struct _pacc_coord. Both line and col are 1-based. */");++nr;
puts("");++nr;
puts("static struct _pacc_coord _pacc_coords(struct pacc_parser *p, size_t col) {");++nr;
puts("    unsigned int i;");++nr;
puts("    int x, y, hi, lo;");++nr;
puts("    struct _pacc_coord_memo *c, *cs = p->coord;");++nr;
puts("");++nr;
puts("    /* binary search */");++nr;
puts("    lo = 0; hi = p->coord_valid;");++nr;
puts("    while (lo < hi) {");++nr;
puts("        int mid = (lo + hi) / 2;");++nr;
puts("        c = cs + mid;");++nr;
puts("        if (c->n < col) lo = mid + 1;");++nr;
puts("        else if (c->n > col) hi = mid;");++nr;
puts("        else return c->c;");++nr;
puts("    }");++nr;
puts("");++nr;
puts("    /* increase list if necessary */");++nr;
puts("    if (p->coord_valid + 1 > p->coord_alloc) {");++nr;
puts("        struct _pacc_coord_memo *n;");++nr;
puts("        p->coord_alloc = p->coord_alloc * 2 + 1;");++nr;
puts("        n = realloc(p->coord, p->coord_alloc * sizeof *n);");++nr;
puts("        if (!n) pacc_nomem();");++nr;
puts("        cs = p->coord = n;");++nr;
puts("    }");++nr;
puts("");++nr;
puts("    /* move hole to the right place */");++nr;
puts("    memmove(cs + lo + 1, cs + lo, (p->coord_valid - lo) * sizeof *cs);");++nr;
puts("    ++p->coord_valid;");++nr;
puts("");++nr;
puts("    /* find the coordinates */");++nr;
puts("    c = cs + lo; c->n = col;");++nr;
puts("    if (lo > 0) {");++nr;
puts("        /* start from last position */");++nr;
puts("        struct _pacc_coord_memo *l = cs + lo - 1;");++nr;
puts("        y = l->c.line; x = l->c.col; i = l->n;");++nr;
puts("    } else {");++nr;
puts("        /* 1-based counting for rows and columns */");++nr;
puts("        y = 1; x = 1; i = 0;");++nr;
puts("    }");++nr;
puts("    while (i < col) {");++nr;
puts("        uint32_t c;");++nr;
puts("        int l = _pacc_utf8_char(p->string + i, p->input_length - i, &c);");++nr;
puts("        if (!l) pacc_panic(\"invalid UTF-8 input\");");++nr;
puts("        i += l;");++nr;
puts("        ++x;");++nr;
puts("        if (c == '\\n') { ++y; x = 1; }");++nr;
puts("    }");++nr;
puts("");++nr;
puts("    /* memoize them */");++nr;
puts("    c->c.line = y;");++nr;
puts("    c->c.col = x;");++nr;
puts("    return c->c;");++nr;
puts("}");++nr;
puts("/* The userland version */");++nr;
puts("#define PACC_LINE (_pacc_coords(_pacc, _x).line)");++nr;
puts("#define PACC_COL (_pacc_coords(_pacc, _x).col)");++nr;
puts("");++nr;
puts("static void pacc_pr(char **buf, size_t *l, char *fmt, ...) {");++nr;
puts("    size_t n;");++nr;
puts("    va_list argp;");++nr;
puts("");++nr;
puts("    va_start(argp, fmt);");++nr;
puts("    n = vsnprintf(0, 0, fmt, argp);");++nr;
puts("    va_end(argp);");++nr;
puts("");++nr;
puts("    *buf = realloc(*buf, *l + n + 1);");++nr;
puts("    if (!buf) pacc_nomem();");++nr;
puts("");++nr;
puts("    va_start(argp, fmt);");++nr;
puts("    vsnprintf(*buf + *l, n + 1, fmt, argp);");++nr;
puts("    va_end(argp);");++nr;
puts("    *l += n;");++nr;
puts("}");++nr;
puts("");++nr;
puts("char *PACC_SYM(pos)(struct pacc_parser *p, const char *s) {");++nr;
puts("    struct _pacc_coord c;");++nr;
puts("    size_t l = 0;");++nr;
puts("    char *r = 0;");++nr;
puts("");++nr;
puts("    c = _pacc_coords(p, p->err_col);");++nr;
puts("    pacc_pr(&r, &l, \"%d:%d: %s\", c.line, c.col, s);");++nr;
puts("");++nr;
puts("    return r;");++nr;
puts("}");++nr;
puts("");++nr;
puts("char *PACC_SYM(error)(struct pacc_parser *p) {");++nr;
puts("    size_t i, l = 0;");++nr;
puts("    char *r = 0;");++nr;
puts("");++nr;
puts("    /* XXX this, or something like it, is very handy, and needs to go");++nr;
puts("     * in. But we're holding off for now as all failing test cases would");++nr;
puts("     * need to be changed. */");++nr;
puts("    //printf(\"got `%c', \", p->string[p->err_col]); /* XXX UTF-8? */");++nr;
puts("");++nr;
puts("    if (p->err_valid && p->err[0][0] == '.')");++nr;
puts("        pacc_pr(&r, &l, \"expected \");");++nr;
puts("    for (i = 0; i < p->err_valid; ++i) {");++nr;
puts("        char *s = p->err[i];");++nr;
puts("        if (*s == '.') ++s;");++nr;
puts("        for ( ; *s; ++s) {");++nr;
puts("            if (isprint(*s)) pacc_pr(&r, &l, \"%c\", *s);");++nr;
puts("            else switch (*s) {");++nr;
puts("                case '\\n':");++nr;
puts("                    pacc_pr(&r, &l, \"\\\\n\");");++nr;
puts("                    break;");++nr;
puts("                default:");++nr;
puts("                    pacc_pr(&r, &l, \"\\\\x%02x\", *s);");++nr;
puts("                    break;");++nr;
puts("            }");++nr;
puts("        }");++nr;
puts("");++nr;
puts("        if (i + 1 < p->err_valid) {");++nr;
puts("            pacc_pr(&r, &l, \", \");");++nr;
puts("            if (i + 2 == p->err_valid) pacc_pr(&r, &l, \"or \");");++nr;
puts("        }");++nr;
puts("    }");++nr;
puts("    return PACC_SYM(pos)(p, r);");++nr;
puts("    //printf(\"%s\\n\", r);");++nr;
puts("    //printf(\"(column %ld)\\n\", _pacc->err_col);");++nr;
puts("}");++nr;
puts("");++nr;
puts("int PACC_SYM(parse)(struct pacc_parser *_pacc) {");++nr;
puts("    enum pacc_status _status;");++nr;
puts("    int _cont = -1, _st, _pacc_any_i, _evaling = 0;");++nr;
puts("    size_t _x = 0, _x_rule, _pos, _pacc_ev_i;");++nr;
puts("    uint32_t _pacc_utf_cp;");++nr;
puts("");++nr;
puts("#if 0");++nr;
puts("    fprintf(stderr, \"sizeof mid %ld, sizeof blk %ld, mids/blk %ld\\n\",");++nr;
puts("            sizeof(struct pacc_mid), sizeof(struct pacc_blk),");++nr;
puts("            pacc_MIDS_PER_BLK);");++nr;
puts("    fprintf(stderr, \"bucket count is %d\\n\", _pacc->m_bkt_cnt);");++nr;
puts("#endif");++nr;
puts("");++nr;
}
void post_engine(void) {
puts("");++nr;
puts("    _x = 0;");++nr;
puts("    cur = _pacc_result(_pacc, _x, start_rule_id);");++nr;
puts("    /* pacc grammars are anchored on the right */");++nr;
puts("    if ((cur->rule & 3) == parsed && cur->remainder != _pacc->input_length) {");++nr;
puts("        _pacc_error(_pacc, \".end-of-input\", cur->remainder);");++nr;
puts("        cur->rule = (cur->rule & ~3) | no_parse;");++nr;
puts("    }");++nr;
puts("    if (!_evaling && (cur->rule & 3) == parsed) {");++nr;
puts("        unsigned char *stack_save;");++nr;
puts("");++nr;
puts("        PACC_TRACE fprintf(stderr, \"PARSED! Time to start eval...\\n\");");++nr;
puts("        _evaling = 1;");++nr;
puts("        _pacc_ev_i = 0;");++nr;
puts("    eval_loop:");++nr;
puts("        PACC_TRACE fprintf(stderr, \"eval loop with _pacc_ev_i == %zu\\n\",");++nr;
puts("                _pacc_ev_i);");++nr;
puts("        stack_save = _pacc->sp;");++nr;
puts("    eval1:");++nr;
puts("        while (_pacc_ev_i < cur->ev_valid) {");++nr;
puts("            int col, rule;");++nr;
puts("            rule = cur->evlis[_pacc_ev_i].call_id;");++nr;
puts("            col = cur->evlis[_pacc_ev_i].col;");++nr;
puts("            ++_pacc_ev_i;");++nr;
puts("            PACC_TRACE fprintf(stderr, \"eval loop: r%d @ c%d\\n\", rule, col);");++nr;
puts("            _pacc_Push(cur);");++nr;
puts("            _pacc_Push(_pacc_ev_i);");++nr;
puts("            cur = _pacc_result(_pacc, col, rule);");++nr;
puts("            _pacc_ev_i = 0;");++nr;
puts("        }");++nr;
puts("        if ((cur->rule & 3) != evaluated && cur->expr_id) {");++nr;
puts("            _x = cur->col;");++nr;
puts("            _st = cur->expr_id;");++nr;
puts("            goto top;");++nr;
puts("        }");++nr;
puts("    _pacc_expr_done:");++nr;
puts("        cur->rule = (cur->rule & ~3) | evaluated;");++nr;
puts("        if (_pacc->sp != stack_save) {");++nr;
puts("            _pacc_Pop(_pacc_ev_i);");++nr;
puts("            _pacc_Pop(cur);");++nr;
puts("            goto eval1;");++nr;
puts("        }");++nr;
puts("        PACC_TRACE fprintf(stderr, \"eval finished\\n\");");++nr;
puts("        goto contin;");++nr;
puts("    }");++nr;
puts("");++nr;
puts("    PACC_TRACE {");++nr;
puts("        unsigned int min, max;");++nr;
puts("        unsigned int i;");++nr;
puts("        unsigned long a, v;");++nr;
puts("");++nr;
puts("        a = v = 0;");++nr;
puts("        min = -1; max = 0;");++nr;
puts("        for (i = 0; i < _pacc->m_bkt_cnt; ++i) {");++nr;
puts("            unsigned int valid = _pacc->m_bkt[i].valid;");++nr;
puts("            unsigned int alloc;");++nr;
puts("");++nr;
puts("            alloc = _pacc_MIDS_PER_BLK * ((valid % _pacc_MIDS_PER_BLK != 0) + valid / _pacc_MIDS_PER_BLK);");++nr;
puts("            fprintf(stderr, \"%d/%d \", valid, alloc);");++nr;
puts("            v += valid; a += alloc;");++nr;
puts("            if (valid < min)");++nr;
puts("                min = valid;");++nr;
puts("            if (valid > max)");++nr;
puts("                max = valid;");++nr;
puts("        }");++nr;
puts("        fprintf(stderr, \"\\n\");");++nr;
puts("        fprintf(stderr, \"used %u buckets\\n\", _pacc->m_bkt_cnt);");++nr;
puts("        fprintf(stderr, \"chain length from %d to %d\\n\", min, max);");++nr;
puts("        fprintf(stderr, \"total used/allocated: %ld/%ld\\n\", v, a);");++nr;
puts("        fprintf(stderr, \"coord_valid: %zu\\n\", _pacc->coord_valid);");++nr;
puts("        fprintf(stderr, \"coord_alloc: %zu\\n\", _pacc->coord_alloc);");++nr;
puts("    }");++nr;
puts("");++nr;
puts("    if ((cur->rule & 3) == evaluated) {");++nr;
puts("        PACC_TRACE fprintf(stderr, \"parsed with value \" TYPE_PRINTF \"\\n\", cur->value.u0); /* XXX u0 */");++nr;
puts("        _pacc->value = cur->value.u0;");++nr;
puts("    } else if ((cur->rule & 3) == parsed) {");++nr;
puts("        PACC_TRACE fprintf(stderr, \"parsed with void value\\n\");");++nr;
puts("    } else PACC_TRACE fprintf(stderr, \"not parsed\\n\");");++nr;
puts("    return (cur->rule & 3) == evaluated;");++nr;
puts("}");++nr;
puts("");++nr;
puts("PACC_TYPE PACC_SYM(result)(struct pacc_parser *p) {");++nr;
puts("    return p->value;");++nr;
puts("}");++nr;
puts("");++nr;
puts("int PACC_SYM(wrap)(const char *name, char *addr, size_t l, PACC_TYPE *result) {");++nr;
puts("    int parsed;");++nr;
puts("    struct pacc_parser *p;");++nr;
puts("");++nr;
puts("    p = PACC_SYM(new)();");++nr;
puts("");++nr;
puts("    PACC_SYM(input)(p, addr, l);");++nr;
puts("    parsed = PACC_SYM(parse)(p);");++nr;
puts("    if (parsed) *result = PACC_SYM(result)(p);");++nr;
puts("    else {");++nr;
puts("        char *e = PACC_SYM(error)(p);");++nr;
puts("        fprintf(stderr, \"%s:%s\\n\", name, e);");++nr;
puts("        free(e);");++nr;
puts("    }");++nr;
puts("");++nr;
puts("    PACC_SYM(destroy)(p);");++nr;
puts("");++nr;
puts("    return parsed;");++nr;
puts("}");++nr;
}
